1. Field of the Invention
The present invention relates to a method for calculating an activity degree of a method in order to effectively select a method for discarding a code.
2. Background of the Invention
Presently, Java(trademark) is widely used not only as a common language for network computing but also as a standard object-oriented language not dependent on any platform. A program written in Java(trademark) is translated into a bytecode which is executed by a Java(trademark) virtual machine. Accordingly, a program once written in Java(trademark) has an advantage that it operates on any computer supporting Java(trademark) regardless of its CPU.
Despite execution of a bytecode by a virtual machine is inferior to direct execution of a machine language code in terms of execution performance. Thus, in general, the bytecode is translated into a machine language code (hereafter referred to as xe2x80x9cJITed codexe2x80x9d) by a JIT compiler during operation of a Java(trademark) program as to execute a JITed code instead of a bytecode. The minimum unit of compilation is a subroutine called a method. A frequently executed code is translated into a machine language so that performance of a machine language code may be exploited while preserving multi-platform characteristics of a Java(trademark) bytecode.
A JITed code for a method is equal to an optimization code generated by a C compiler and so on on the point of being a code suited to a CPU on which a program operates. In general, in the currently popular CPUs, if a subroutine is invoked, the subroutine forms a stack of an area (referred to as a xe2x80x9cframexe2x80x9d) for storing a local variable to be used by itself. FIG. 1 shows a state of a stack when subroutine A has invoked subroutine B and subroutine B has invoked subroutine C. In this drawing, the stack extends upward. The areas represent respective frames of the subroutines. When returning from each subroutine, its frame is removed. In the case of Java(trademark), CPU resources are allocated to each executable unit called a thread which has its own stack (referred to as a xe2x80x9cthread stackxe2x80x9d). A JITed code creates the above-mentioned frame (hereafter referred to as xe2x80x9cJITed framexe2x80x9d) on a thread stack.
While, in most cases, a method is initially executed by an interpreter, it is compiled by a JIT compiler if determined that it is executed more than a certain level in terms of execution frequency or execution time. Once generated, JITed codes are managed in memory. The time when a Java(trademark) system assures that they can be safely discarded is when the Java(trademark) system discards a class (hereafter xe2x80x9cclass unloadxe2x80x9d) by garbage collection (hereafter xe2x80x9cGCxe2x80x9d).
There are cases where, if the memory used by a JIT compiler including a JITed code is limited or to be limited, only class unload is not sufficient. For instance, in a desktop environment where operation is on a thin client without any virtual memory by a hard disk such as a network computing machine (hereafter an xe2x80x9cNC machinexe2x80x9d), memory limitation is a realistic problem. In such a desktop environment, multiple Java(trademark) applications such as a mail, a word processor, and a scheduler are simultaneously activated and thousand of types of methods may be invoked, though a significant percentage of those methods are not present (are not active) in each thread stack. Since class unload only discards a class and its method with no possibility of being fully used in a Java(trademark) system, a JITed code of such a nonactive method is not discarded. Thus, a JIT compiler has a mechanism of JITed code discarding.
In a current context (a program counter) or a stack pointer of a thread during execution and the like (copies of CPU resources) or a frame of a JITed code held in such a thread stack, an active method in the thread is recorded. If a JITed code of an active method is discarded, a thread cannot be executed. Accordingly, it is a nonactive JITed code that is discarded. The easiest way of discarding in JITed code discarding is to discard all nonactive JITed codes. However, this method is wasteful since more than necessary JITed codes are discarded. Since optimizing compilation of a method takes time, they should be selectively discarded under a policy of xe2x80x9ca method to be promptly executed is not discarded.xe2x80x9d As an example of an effect of accurate selection, it is assumed that there are method A wherein JITed code discarding is performed now and immediately executed and method B wherein it is executed then minutes later. If A is discarded, the amount of memory of a JITed code of A which was just discarded and the amount of memory necessary for compilation work of A must be immediately secured. On the other hand, if B is discarded, the amount of memory of a JITed code of B becomes available memory for ten minutes. In reality, multiple JITed codes equal to the necessary amount of free memory are discarded. While an ideal policy of discarding is to discard JITed codes to be no longer used, such information is normally unavailable. It is more realistic to infer it and discard them in order of the least recently used method. Hereafter, it is called the JITed code discarding policy.
There are execution frequency (how many times it was called) and execution time (the time a program counter was pointing the method) among normally thinkable profiles of a method. Collection of execution frequency is performed by increasing a counter of a method every time the method is called. If the method is compiled by a JIT compiler, updating of execution frequency measured by an interpreter until then is terminated, so execution frequency information for a JITed code cannot be obtained from the interpreter. To obtain execution frequency information for a JITed code, it is necessary to count execution times at a prologue of a JITed code of each method. For instance, on a x86 platform, inc dword ptr [counter address] instruction is added. Collection of execution time is performed by interrupting (typically timer interruption, or executable instructions interruption depending on a processor) at regular intervals and collecting program counters (hereafter xe2x80x9cpcxe2x80x9d).
If these conventional profiles are used as a JITed code discarding policy, a problem arises. First, as to execution frequency, it is a problem to refer to memory and count it each time a JITed code of each method is executed because it causes overhead to a state where memory is not exhausted. Moreover, there is a possibility of mistakenly discarding a method with low frequency but to be immediately called. Since what is necessary is a JITed code occupying memory without being called, it is beside the object. Also, as to execution time, interruption and management of collected pc (cost of association if immediately associated, or retention if not) are problematic because they cause overhead to a state where memory is not exhausted. In addition, similar to the case of collecting execution frequency, there is a possibility of mistakenly discarding a method with short execution time but to be immediately called.
As mentioned above, it is irrelevant to adopt a conventional profile method as a JITed code discarding policy, and it may cause an inadequate JITed code discarding. An object of the present invention is to provide a method for calculating an activity degree of a method representing how readily it can be performed in order to effectively select a method for discarding a code.
To attain the above object, at a compilation time, the present invention generates and stores into a storage a calling map concerning a method call which may happen in a method, and generates and stores into a storage a code for recording a method call which is actually issued. This calling map is organized, for a certain address in a method, to be suitable for outputting any method call which may happen from the address onward. However, it is also possible to output method calls for each method. Once compilation ends and a generated code is executed, a calling map concerning method calls which may happen in a method and information concerning method calls which are actually issued are recorded for each method.
To discard a code in such a state, all threads are temporarily stopped and the activity degree of each method indicating a possibility that the method is actually called is calculated. At this time, a second method which has a high possibility that the second method is actually called from a first method corresponding to a stack frame is specified and stored into a storage by using the calling map and information concerning method calls which are actually issued for the first method, and an activity degree of the second method is updated by operating a priority corresponding to the number of stages of the stack frame corresponding to the first method from the top of a stack to the activity degree of the second method. Suitably, such a process is repeated. Namely, a third method which has a high possibility that the third method is actually called from the second method is specified and stored into a storage by using the calling map and information concerning method calls which are actually issued for the second method, and an activity degree of the third method is updated by operating a priority corresponding to the number of stages of the stack frame corresponding to the first method from the top of a stack to the activity degree of the third method. A code of any method acquired in this way whose activity degree is low is discarded so as to enable more efficient code discarding.
Moreover, suitably, a calling map outputs to a certain address in a method a method call which may happen from the address onward, and a second method is specified by using a method call which may happen from the execution restarting address of a first method onward.
The present invention seeks by utilizing a current context, a program structure, and execution time information a degree of how readily a nonactive method is called (an activity degree). Utilization of a current context referred to here means being possible to determine that the higher (near the top) order a method has in a stack, the earlier it is to be executed. Utilization of a program structure means knowing for a control flow methods likely to be called from now on out of those temporarily stopped. Utilization of execution time information means that even the method likely to be called (including an interpreter) may be excluded from determination subjects if not called at all at runtime. An activity degree of a method likely to be called early is raised according to how early it is called.
Thus, as to an activity degree, the earlier re-execution time of a method is, the larger its value becomes. This is good in terms of well imitating the above-mentioned JITed code discarding policy. In the case of the aforementioned example, if A and B are the methods called from a high order and a low order in a stack respectively, A""s activity degree becomes higher than that of B due to algorithm of the present invention, so there will be no case where A is selected and discarded prior to B.
If a memory request of a JIT compiler cannot be met in a certain thread, the thread temporarily stops all the threads other than itself and locates active methods. A method for calculating an activity degree of a method of the present invention is used to decide an activity degree of each method. Thereafter, based on such an activity degree, some or all of JITed codes of a nonactive method are discarded. All temporarily stopped threads are restarted and memory is requested again. This is repeated until the memory request is met. If the memory request is not finally met, and if allowed, an optimization level of the compiler is lowered and compilation is challenged again. If compilation is not allowed agin, or if compilation is not possible even at the lowest optimization level, this method is not compiled.
To reduce working cost for calculating activity degrees of methods, an upper limit may be set to frequency of operation for their activity degrees to be operated to an activity degree of any method further called by them.